#ifndef cursorList_H
#define cursorList_H
#include <stdexcept>
#include <vector>
using namespace std;

template <class Object>
class List;

template <class Object>
class ListItr
{
  public:
  	ListItr(): current(0)
	{
	}

	bool isPastEnd() const
	{
		return current == 0;	
	}

	void advance()
	{
		if (!isPastEnd())	
			current = List<Object>::cursorSpace[current].netx;
	}

	const Object & retrieve() const
	{
		if (isPastEnd())	
			//throw BadIterator();
			throw range_error("past end");
		return List<Object>::cursorSpace[current].element;
	}

  private:
  	int current;
	friend class List<Object>;

	ListItr(int theNode): current(theNode) {}
};

template <class Object>
class List
{
  public:
  	List();
	List(const List & rhs);
	~List();

	bool isEmpty() const;
	void makeEmpty();
	ListItr<Object> zeroth() const;
	ListItr<Object> first() const;
	void insert(const Object &x, const ListItr<Object> &p);
	ListItr<Object> find(const Object & x) const;
	ListItr<Object> findPrevious(const Object &x) const;
	void remove(const Object &x);

  public:
	struct CursorNode
	{
		CursorNode(): next(0) {}	
		
	  private:
	  	CursorNode(const Object &theElement, int n)
		  : element(theElement), next(n) {}

		Object element;
		int next;

		friend class List<Object>;
		friend class ListItr<Object>;
	};

	const List & operator=(const List &rhs);
  
  private:
  	int header;

	static vector<CursorNode> cursorSpace;
	static void initializeCursorSpace();
	static int alloc();
	static void free(int p);

	friend class ListItr<Object>;
};
#endif
